﻿
using System;
using System.Collections;
using System.Collections.Generic;


public class HeapQ<T> where T : IComparable
{
	List<T> items;

	public HeapQ ()
	{
		items = new List<T> ();
	}

	public bool Empty {
		get { return items.Count == 0; }
	}

	public List<T> getData()
	{
		return items;
	}

	public void clear()
	{
		items.Clear ();
	}

	public int Length()
	{
		return items.Count;
	}

	public T First {
		get {
			if (items.Count > 1) {
				return items[0];
			}
			return items[items.Count - 1];
		}
	}

	public void Push (T item)
	{
		items.Add (item);
		SiftDown (0, items.Count - 1);
	}

	public T Pop ()
	{
		T item;
		var last = items[items.Count - 1];
		items.RemoveAt (items.Count - 1);
		if (items.Count > 0) {
			item = items[0];
			items[0] = last;
			SiftUp (0);
		} else {
			item = last;
		}
		return item;
	}

	void SiftDown (int startpos, int pos)
	{
		var newitem = items[pos];
		while (pos > startpos) {
			var parentpos = (pos - 1) >> 1;
			var parent = items[parentpos];
			if (parent.CompareTo (newitem) <= 0)
				break;
			items[pos] = parent;
			pos = parentpos;
		}
		items[pos] = newitem;
	}

	void SiftUp (int pos)
	{
		var endpos = items.Count;
		var startpos = pos;
		var newitem = items[pos];
		var childpos = 2 * pos + 1;
		while (childpos < endpos) {
			var rightpos = childpos + 1;
			if (rightpos < endpos && items[rightpos].CompareTo (items[childpos]) <= 0)
				childpos = rightpos;
			items[pos] = items[childpos];
			pos = childpos;
			childpos = 2 * pos + 1;
		}
		items[pos] = newitem;
		SiftDown (startpos, pos);
	}

}